package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/linked-list-cycle/">环形链表 [简单]</a>
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 * 说明：
 * 链表中节点的数目范围是 [0, 104]
 * -105 <= Node.val <= 105
 * pos 为 -1 或者链表中的一个 有效索引 。
 *
 * @author zhenzicheng
 * @date: 2022-06-01 22:10
 */
public class LinkedListCycle_141 {

  /**
   * 使用快慢指针，如果有环形结构，那么快指针一定会追上慢指针
   */
  public boolean hasCycle(ListNode head) {
    if (head == null) {
      return false;
    }
    // 定义快指针，将head当成慢指针
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
      head = head.next;
      fast = fast.next.next; // 保证每次快指针比慢指针多走
      if (head == fast) {
        return true;
      }
    }
    return false;
  }

  /**
   * 不需要提交
   */

}
